ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpa/subseq/test.cpp

   1 #include <stdio.h>
   2 #include <vector>
   3 #include <string>
   4 #include <iostream>
   5 #include <cassert>
   6
   7 using namespace std;
   8
   9 typedef unsigned int uint32;
  10
  11 #define forsn(i, s, n)  for (uint32 i = (s); i < (n); i++)
  12 #define forn(i, n)      forsn (i, 0, n)
  13 #define fordn(i, n)     for (uint32 i = (n); i-- > 0;)
  14
  15 // BigInt
  16 // Represents a number in 0 <= n < 10 ** 128
  17
  18 #define BigInt_NDIGITS  16
  19 #define BigInt_BASE     100000000
  20 class BigInt {
  21 public:
  22         BigInt() : _digits(BigInt_NDIGITS, 0) {}
  23
  24         BigInt(uint32 n) : _digits(BigInt_NDIGITS, 0) {
  25                 assert(n < BigInt_BASE);
  26                 _digits[0] = n;
  27         }
  28
  29 #if 0
  30         // Test BigInt
  31         BigInt(const string& s) : _digits(BigInt_NDIGITS, 0) {
  32                 uint32 pow = 1;
  33                 uint32 digit = 0;
  34                 uint32 j = 0;
  35                 fordn (i, s.size()) {
  36                         assert('0' <= s[i] && s[i] <= '9');
  37                         digit += pow * (s[i] - '0');
  38
  39                         pow *= 10;
  40                         if (pow == BigInt_BASE) {
  41                                 _digits[j++] = digit;
  42                                 digit = 0;
  43                                 pow = 1;
  44                         }
  45                 }
  46                 assert(j < BigInt_NDIGITS || digit == 0);
  47                 if (j < BigInt_NDIGITS) {
  48                         _digits[j] = digit;
  49                 }
  50         }
  51 #endif
  52
  53         BigInt operator+(const BigInt& n) {
  54                 BigInt res;
  55                 bool carry = 0;
  56
  57                 forn (i, BigInt_NDIGITS) {
  58                         const uint32 r = _digits[i] + n._digits[i] + carry;
  59                         if (r >= BigInt_BASE) {
  60                                 res._digits[i] = r % BigInt_BASE;
  61                                 assert(r / BigInt_BASE == 1);
  62                                 carry = 1;
  63                         } else {
  64                                 res._digits[i] = r;
  65                                 carry = 0;
  66                         }
  67                 }
  68                 assert(carry == 0);
  69                 return res;
  70         }
  71
  72         void print() {
  73                 bool zero = true;
  74                 fordn (i, BigInt_NDIGITS) {
  75                         if (zero) {
  76                                 if (_digits[i] == 0) continue;
  77                                 printf("%u", _digits[i]);
  78                                 zero = false;
  79                         } else {
  80                                 printf("%.8u", _digits[i]);
  81                         }
  82                 }
  83                 if (zero) {
  84                         printf("0");
  85                 }
  86         }
  87
  88 private:
  89         // Least significant digit first.
  90         // Digits are in 0 <= d < BigInt_BASE
  91         vector<uint32> _digits;
  92 };
  93
  94 #define print_bigint(x) (x).print()
  95
  96 typedef vector<BigInt> vBigInt;
  97 typedef vector<vBigInt> vvBigInt;
  98 BigInt distinct_subsequences(const string& x, const string& z) {
  99         vvBigInt m(2, vBigInt(z.size() + 1, BigInt(0)));
 100
 101         m[0][0] = BigInt(1);
 102         m[1][0] = BigInt(1);
 103         bool row = 1;
 104         forsn (i, 1, x.size() + 1) {
 105                 forsn (j, 1, z.size() + 1) {
 106                         if (x[i - 1] == z[j - 1]) {
 107                                 m[row][j] = m[!row][j] + m[!row][j - 1];
 108                         } else {
 109                                 m[row][j] = m[!row][j];
 110                         }
 111                 }
 112                 row = !row;
 113         }
 114         return m[!row][z.size()];
 115 }
 116
 117
 118 struct Prefijo{
 119         BigInt cantidad;
 120         Prefijo* previo;
 121 };
 122
 123 void contar_substrings(string x, string z){
 124
 125         // Diccionario para poder acceder en O(1) a los prefijos que terminan en cierta letra
 126         list<Prefijo*> diccionario[26];
 127
 128         // Inicializamos el diccionario
 129         int i = 0;
 130         while(i < 26){
 131                 diccionario[i] = list<Prefijo*>();
 132                 i++;
 133         }
 134
 135         string::iterator it;
 136         Prefijo * anterior = 0;
 137         /*
 138         Idea: para guardar un prefijo me alcanza conocer cual era el prefijo anterior (una letra menos) y cual es su ultima letra
 139         */
 140         foreachin(it,z){
 141                         Prefijo* aux = new Prefijo;
 142                         aux->cantidad = BigInt(0);
 143                         aux-> previo = anterior;
 144                         diccionario[*it-97].push_front(aux);
 145                         anterior = aux;
 146
 147         }
 148
 149         foreachin(it,x){
 150                 list<Prefijo*>::iterator it2;
 151
 152                 foreachin(it2,(diccionario[*it-97])){
 153                         // Si es el prefijo de una sola letra, encontre uno mas
 154                         if((*it2)->previo == 0)(*it2)->cantidad=(*it2)->cantidad + BigInt(1);
 155                         // Sino, tengo tantos como tenia mas la cantidad de prefijos de una letra menos, que ahora se completan
 156                         else (*it2)->cantidad= (*it2)->cantidad + (*it2)->previo->cantidad;
 157                 }
 158         }
 159
 160         char ultimo = *(--z.end());
 161         print_bigint((*(diccionario[ultimo - 97].begin()))->cantidad);
 162
 163
 164         foreachin(it,z){
 165                 list<Prefijo*>::iterator it2;
 166                 Prefijo* aux = diccionario[*it-97].front();
 167                 diccionario[*it-97].pop_front();
 168                 delete aux;
 169         }
 170
 171 }
 172
 173 int main(int argc, char **argv) {
 174 #if 0
 175         // Test BigInt
 176         if (argc == 2) {
 177                 BigInt a(argv[1]);
 178                 a.print();
 179                 printf("\n");
 180         } else if (argc == 3) {
 181                 BigInt a(argv[1]);
 182                 BigInt b(argv[2]);
 183                 BigInt c = a + b;
 184                 c.print();
 185                 printf("\n");
 186         }
 187 #endif
 188         uint32 n;
 189         cin >> n;
 190         char c;
 191         cin.get(c);
 192         forn (i, n) {
 193                 string x, z;
 194                 getline(cin, x);
 195                 getline(cin, z);
 196                 //print_bigint(distinct_subsequences(x, z));
 197                 contar_substrings(x,z);
 198                 cout << endl;
 199         }
 200         return 0;
 201 }
 202